package com.zlk.algorithm.huawei.leetcode.dimidiate;

import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName Code57_searchInsert
 * @description:
 * @author: slfang
 * @create: 2025-01-19 21:20
 * @Version 1.0
 **/
public class Code57_searchInsert {

    @Test
    public void test(){
        System.out.println(searchInsert(new int[]{1,3,5,6}, 7));
    }


    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }


    public int searchInsert1(int[] nums, int target) {
        return findLeftIndex(nums,target);
    }

    private int findLeftIndex(int[] nums, int target) {
        int l=0;
        int r=nums.length-1;
        int mid;
        int ans=-1;
        while (l<=r){
            mid =l+(r-l)/2;
//            if(nums[mid]==target){
//                ans = mid;
//                break;
//            }else
            if(nums[mid]>=target){
                //左边
                ans = mid;
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        return ans==-1?nums.length:ans;
    }
}
